package com.explorati.LeetCode438.findallanagramsinastring;

import java.util.ArrayList;
import java.util.List;

public class Solution1 {
	public static List<Integer> findAnagrams(String s, String p) {
		ArrayList<Integer> rst = new ArrayList<Integer>();
		if (s == null || p == null || s.length() < p.length()) {
			return rst;
		}
		int[] hash = new int[128];
		char[] t = s.toCharArray(), q = p.toCharArray();
		for (char c : q) {
			hash[c]++;
		}

		int start = 0, end = 0, count = p.length(), lenS = s.length(), lenP = p.length();
		while (end < lenS) {
			if (hash[t[end]] >= 1) {
				count--;
			}
			hash[t[end]]--;
			end++;
			if (count == 0) {
				rst.add(start);
			}
			if (end - start == lenP) {
				if (hash[t[start]] >= 0) {
					count++;
				}
				hash[t[start]]++;
				start++;
			}
		}
		return rst;
	}

	public static void main(String[] args) {
		// String s = "cbaebabacd";
		String s = "abab";
		String p = "ab";
		List<Integer> list = findAnagrams(s, p);
		for (int i : list) {
			System.out.print(i + "  ");
		}
	}
}
